package cn.edu.jxau.test;

import java.util.Arrays;

/**
 * 加权 压缩 quick-union实现
 * @author 付大石
 */
public class UnionFind {

    /**
     * 触点集
     */
    private int[] idArr;

    /**
     * 连通分量个数
     */
    private int count;

    public UnionFind(int count) {

        this.count = count;
        idArr = new int[count];
        for (int i = 0; i < idArr.length; i++) {
            idArr[i] = i;
        }
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int find(int p) {

        while (idArr[p] != p) {
            idArr[p] = idArr[idArr[p]]; // 路径压缩，用于构造一棵超级超级扁平的树
            p = idArr[p];
        }
        return p;
    }

    public int count() {
        return count;
    }

    public void union(int p, int q) {

        int pRoot = find(p); // p连通分量
        int qRoot = find(q); // q连通分量
        if (pRoot == qRoot) {
            return;
        }

        // 连接两个连通分量 //
        idArr[pRoot] = qRoot; // 将p连通分量连到q连通分量上
        count--;
    }

    @Override
    public String toString() {

        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("count:").append(count).append("\t");
        stringBuilder.append(Arrays.toString(idArr));
        return stringBuilder.toString();
    }
}
